The present invention relates generally to identifying information in a compressed bit-stream and more particularly to identifying a desired segment of a compressed bit-stream. The invention is particularly suitable for use in identify a desired frame or shot in an encoded video sequence, such as a high definition television (HDTV) broadcast signal or other compressed form of video information as might be communicated via the INTERNET or other communications network.
Basic standards for compressing the bandwidth of digital color video signals have been adopted by the Motion Picture Experts Group (MPEG). The MPEG standards achieve high data compression rates by developing information for a full frame of the image only every so often. The full image frames, i.e. intra-coded frames, are often referred to as xe2x80x9cI-framesxe2x80x9d or xe2x80x9canchor framesxe2x80x9d, and contain full frame information independent of any other frames. Image difference frames, i.e. inter-coded frames, are often referred to as xe2x80x9cB-framesxe2x80x9d and xe2x80x9cP-framesxe2x80x9d, or as xe2x80x9cpredictive framesxe2x80x9d, and are encoded between the I-frames and reflect only image differences i.e. residues, with respect to the reference frame.
Typically, each frame of a video sequence is partitioned into smaller blocks of picture element, i.e. pixel, data. Each block is subjected to a discrete cosine transformation (DCT) function to convert the statistically dependent spatial domain pixels into independent frequency domain DCT coefficients. Respective 8xc3x978 or 16xc3x9716 blocks of pixels, referred to as macro-blocks, are subjected to the DCT function to provide the coded signal. The DCT coefficients are usually energy concentrated so that only a few of the coefficients in a macro-block contain the main part of the picture information. For example, if a macro-block contains an edge boundary of an object, the energy in that block after transformation, i.e. as represented by the DCT coefficients, includes a relatively large DC coefficient and randomly distributed AC coefficients throughout the matrix of coefficients. A non-edge macro-block, on the other hand, is usually characterized by a similarly large DC coefficient and a few adjacent AC coefficients which are substantially larger than other coefficients associated with that block. The DCT coefficients are typically subjected to adaptive quantization, and then are run-length and variable-length encoded for the transmission medium. Thus, the macro-blocks of transmitted data typically include fewer than an 8xc3x978 matrix of codewords.
The macro-blocks of inter-coded frame data, i.e. encoded P or B frame data, include DCT coefficients which represent only the differences between a predicted pixels and the actual pixels in the macro-block. Macro-blocks of intra-coded and inter-coded frame data also include information such as the level of quantization employed, a macro-block address or location indicator, and a macro-block type. The latter information is often referred to as xe2x80x9cheaderxe2x80x9d or xe2x80x9coverheadxe2x80x9d information.
Each P frame is predicted from the lastmost occurring I or P frame. Each B frame is predicted from an I or P frame between which it is disposed. The predictive coding process involves generating displacement vectors, often referred to as xe2x80x9cmotion vectorsxe2x80x9d, which indicate the magnitude of the displacement to the macro-block of an I frame most closely matches the macro-block of the B or P frame currently being coded. The pixel data of the matched block in the I frame is subtracted, on a pixel-by-pixel basis, from the block of the P or B frame being encoded, to develop the residues.
The transformed residues and the vectors form part of the encoded data for the P and B frames.
With the advent of new digital video services, such as video distribution on the INTERNET, there is an increasing need for signal processing techniques for identifying information in video sequences. For example, identification of scene changes, whether they are abrupt or gradual, and of features or characteristics of a scene are useful for the purposes of indexing image changes so that scenes of interest may be automatically and easily identified. In the future, a significantly greater amount of digital video material will be provided in the form of compressed or encoded data. Operating on the video sequence information in its compressed form, rather than in its decompressed or decoded form, where possible, will permit more rapid processing because of the reduction in data size and processing steps. Hence, a need exists for techniques which permit operating directly on compressed data, rather than having to perform full frame decompression before operating on the data.
Previous work in feature extraction for video indexing from compressed data has primarily emphasized DC coefficient extraction. In a paper entitled xe2x80x9cRapid Scene Analysis on Compressed Videoxe2x80x9d, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 5, No. 6, December 1995, page 533-544, Yeo and Liu describe an approach to scene change detection in the MPEG-2 compressed video domain. The authors also review earlier efforts at detecting scene changes based on sequences of entire uncompressed image data, and various compressed video processing techniques of others. Yeo and Liu introduced the use of spatially reduced versions of the original images, so-called DC images, and DC sequences extracted from compressed video to facilitate scene analysis operations. Their xe2x80x9cDC imagexe2x80x9d is made up of pixels which are the average value of the pixels in a block of the original image and the DC sequence is the combination of the reduced number of pixels of the DC image. It should be noted that the DC image extraction based technique is good for I-frames since the extraction of the DC values from I-frames is relatively simple. However, for other type frames, additional computation is needed.
Won et al, in a paper published in Proc. SPEE Conf. on Storage and Retrieval for Image and Video Databases, January 1998, describe a method of extracting features from compressed MPEG-2 video by making use of the bits expended on the DC coefficients to locate edges in the frames. However, their work is limited to I-frames only. Kobla et al describe a method in the same Proceedings using the DC image extraction of Yeo et al to form video trails that characterize the video clips. Feng et al (IEEE International Conference on Image Processing, Vol. 11, pp. 821-824, Sept. 16-19, 1996), use the bit allocation across the macro-blocks of MPEG-2 frames to detect abrupt scene changes, without extracting DC images. Feng et al""s technique is computationally the simplest since it does not require significant computation beyond that required for parsing the compressed bit-stream.
In accordance with prior work of the present inventors and a co-worker, which is described in previously filed, commonly owned co-pending U.S. Patent applications entitled xe2x80x9cMethods of scene change detection and fade detection for indexing of video sequencesxe2x80x9d (application Ser. No. 09/231,698, filed Jan. 14, 1999), xe2x80x9cMethods of scene fade detection for indexing of video sequencesxe2x80x9d (application Ser. No. 09/231,699, filed Jan. 14, 1999), xe2x80x9cMethods of Feature Extraction for Video Sequences (aplication Ser. No. 09/236,838, Jan. 25, 1999), computationally simple techniques have been devised which build on certain aspects of Feng et al""s approach and Yeo et al""s approach to give accurate and simple scene change detection. Once a suspected scene or object change has been accurately located in a group of consecutive frames by use of a DC image extraction based technique, application of an appropriate bit allocation-based technique and/or an appropriate DC residual coefficient processing technique to P or B-frame information in the vicinity of the located scene quickly and accurately locates the cut point. This combined method is applicable to either MPEG-2 frame sequences or MPEG-4 multiple object sequences. In the MPEG-4 case, it is advantageous to use a weighted sum of the change in each object of the frame, using the area of each object as the weighting factor.
However, notwithstanding the previously developed techniques, a need remains for a simplified technique for identifying a desired frame, object, shot or sequence from a compressed bit-stream.
The present invention is directed to descriptors for frames represented in a compressed bit-stream corresponding to a video sequence including intra-coded frames, e.g. I frames, and inter-coded frames, e.g. B and P frames. It will be understood that, I frames are also referred to as anchor frames and B and P frames are often referred to as predictive frames. As used herein, the term xe2x80x9cframexe2x80x9d includes frames as defined under most current MPEG standards as well as objects as defined under the current MPEG-4 standard. The term is also intended to cover other segmentations of compressed bit-streams as may be defined in future MPEG or similar video standards or other non-video standards.
The invented descriptors can be used to index, select or otherwise identify a desired frame for any number of reasons, as will be well understood by those skilled in the art. For example, the descriptor can be used to identify, from bits of the compressed bit-stream, the frame within the entire sequence or a shot, i.e. a subset of adjacent frames within the video sequence, which most closely matches a query frame, includes an object of interest, or represents the beginning of a new scene.
Compressed bit-streams for video sequences include bits associated with each of the intra-coded and inter-coded frames. With regard to the inter-coded frames, the bits typically represent a number of different parameters, including a displacement from the associated inter-coded frame, e.g. a B or P frame, to a closest matching intra-coded frame, e.g. an I frame. Under conventional NPEG standards, the represented displacement is customarily characterized by a displacement vector, sometimes also referred to as a motion vector.
It will also be recognized that under MPEG standards, e.g. MPEG-2, the displacement to the intra-coded frame may be directly or indirectly represented. More particularly, under most current MPEG protocols, the bits associated with a particular B frame will directly represent a displacement to the applicable I frame. However the bits associated with a particular B frame can also directly represent a displacement to a P frame which has associated bits directly representing a further displacement to the applicable I frame. Hence, in such a case, the bits representing the displacement of the particular B frame of interest will indirectly represent the displacement to the applicable I frame.
In accordance with the invention, the magnitude of the displacement of an inter-coded frame is determined based on the bits in the compressed bit-stream associated with that inter-coded frame. Preferably, the compressed bit-stream is entropy decoded and the displacement magnitude is determined from the entropy decoded compressed bit-stream. The inter-coded frame is then identified based upon the determined displacement magnitude. In other words, the magnitude of displacement determined from the bits of the compressed bit steam serves as a descriptor which is used to identify the inter-coded frame as the desired frame. The displacement magnitude may serve to characterize only the frame itself, or the entire video sequence, or a subset of the sequence, i.e. a particular shot. Thus, using the determined displacement magnitude, the particular frame, the particular shot in a sequence or even the particular sequence in a set of sequences which, for example, most closely matches a query, includes an object of interest, or represents the beginning of a new scene can be identified through the identification of the frame.
For example, to index to the desired frame of a video sequence, the determined magnitude of the displacement, represented by the bits of the compressed bit-stream of each of the frames in the video sequence, may be compared with the magnitude of displacement of a query frame. That frame of the video sequence which has a displacement magnitude which most closely matches the displacement magnitude of the query frame is identified. This frame can now be used for any number of purposes, e.g. to index the video sequence, to retrieve the beginning frame of a scene, or to locate a frame having an image of an object of interest not appearing in preceding frames, etc.
Typically, each of the inter-coded frames will include a plurality of macro-blocks, and each of the macro-blocks will be associated with a respective portion of the bits representing a displacement from the associated macro-block to the closest matching intra-coded frame. In accordance with an aspect of the invention, the displacement magnitude of each inter-coded frame is determined by determining, based on the portion of the bits in the compressed bit-stream associated with that inter-coded frame, an average magnitude of the displacement per macro-block for the frame. This can be accomplished by simply dividing the sum total of the determined displacement magnitudes of all the macro-blocks by the total number of macro-blocks included in the applicable frame. The desired inter-coded frame is then selected based upon the determined average displacement magnitude.
According to further aspects of the invention, the determined displacement magnitude represented by the applicable portion of bits associated with the applicable macro-block is, for example, set to zero if the displacement magnitude for that macro-block is less than a threshold. Preferably, the threshold is the determined average displacement magnitude for the applicable frame. A value corresponding to the run lengths for those macro-blocks having the displacement magnitude less than the threshold is determined. Preferably, the value is equal to the number of the applicable run lengths. For example, the value could be the number 3 indicating that there are 3 run lengths having runs of macro-blocks with a displacement magnitude of less than the threshold. The desired inter-coded frame can then be identified based upon both the determined displacement magnitude, e.g. the average displacement magnitude, and the determined value corresponding to the run lengths. In other words, the magnitude of displacement determined from the bits of the compressed bit steam and the value corresponding to the run lengths determined from the determined displacement magnitudes of the macro-blocks together serve as a descriptor which can be used to identify the desired inter-coded frame. This multi-parameter descriptor provides a somewhat enhanced characterization of the applicable frame as compared to the above described descriptor without the run lengths.
The sum of the determined run lengths will equal the total number of macro-blocks having the displacement magnitude less than the threshold. Beneficially, each of the determined run lengths is categorized in one of multiple categories, each corresponding to a different run length range. Preferably, three categories are used, i.e. short, medium and long length run ranges. The number of run lengths within each of the categories is computed. An inter-coded frame can then be identified based upon the determined displacement magnitude and the determined number of run lengths in each category. That is, the magnitude of displacement and the run lengths in each category can, if desired, serve as the descriptor which is used to identify the desired inter-coded frame. This multi-parameter descriptor may provide an even more enhanced characterization of the applicable frame as compared to the above described multi-parameter descriptor with the run lengths.
To improve accuracy, the descriptor is advantageously normalized. The displacement magnitude is typically normalized based upon the frame width. However, to ensure compatibility with different encoding protocols, the displacement magnitude and the value(s) corresponding to run lengths are preferably normalized based on one or more of the parameters used to encode the encoded bit-stream. More particularly, the magnitude and value are normalized based on the encoding frame format, frame size, frame rate and/or bit rate.
To further improve processing efficiency, the determined displacement magnitude can be combined with the determined run lengths. In this regard, the combination of parameters could, for example, be reduced to only a single value. The combined displacement magnitude and run lengths can then be used to identify the desired inter-coded frame.
As discussed above, the video sequence may include multiple shots, each formed of a respective series of adjacent inter-coded frames. In some cases, it may be desirable to determine not only the average magnitude of displacement per macro-block for the macro-blocks of each of the inter-coded frames forming the shot as described above, but also to determine the average of the average displacement magnitudes per macro-block per frame for all the macro-blocks of the entire shot. In such case, the determined average displacement magnitude per macro-block of each of the inter-coded frames in the shot are, in one alternative implementation, compared to a determined average displacement magnitude per macro-block per frame. The determined average displacement magnitude per macro-block of the inter-coded frame which best represents the shot is then identified based on the comparison. For example, the inter-coded frame within the shot having an average displacement magnitude per macro-block closest to the determined average displacement magnitude per macro-block per frame of the entire shot might be identified as best representing the shot as a whole or some particular content of interest within the shot. Alternatively, a frame, e.g. an arbitrarily selected frame, may be associated with the determined average displacement magnitude per macro-block per frame and identified on the basis of this association, without the above described comparison being performed.
In a preferred embodiment of the invention, a desired frame in a compressed video bit-stream corresponding to a video sequence is identified based on descriptors which are determined from bits of the compressed bit-stream associated with each of the inter-coded frames. The bits represent (i) the magnitude of the displacement per macro-block, for the associated inter-coded frame, to a closest matching of the intra-coded and/or (ii) a value corresponding to, e.g. the number of, run lengths of those of the plurality of macro-blocks of the associated inter-coded frame having a displacement magnitude to a closest matching intra-coded frame equaling less than a threshold amount. Two of the inter-coded frames, or more, are first identified based on the respective displacement magnitude per macro-block of the inter-coded frames. Only one of these inter-coded frames is then identified based on the number of run lengths associated with that inter-coded frame.
According to still another aspect of the invention, the frequency of occurrence of the number of the run lengths associated with each of the two or more inter-coded frames is compared with the frequency of occurrence of the number of the run lengths associated with the other of the two or more inter-coded frames. The desired inter-coded frame is identified based on the differences between the frequencies of occurrence.
The compressed bit-stream can be stored in a memory. A processor can then determine the displacement magnitudes of the inter-coded frames based on the bits in the stored compressed bit-stream and subsequently identify the desired inter-coded frame based on the determined displacement magnitude and/or run lengths as previously described. The processor can, if desired, be further configured to determine average displacement magnitudes, to set the displacement magnitudes which are below a threshold to zero, to determine run lengths for those of the plurality of macro-blocks having their displacement magnitudes equaling less than the threshold, to categorize run lengths, to compute the number of run lengths within each category, and to combine the determined displacement magnitude with the determined run lengths, as has been previously discussed.